package solutions.leetcode.normal;

import solutions.lib.BaseSolution;

/**
 * @author lizhidong
 * <a href="https://leetcode-cn.com/problems/maximum-product-of-word-lengths/">318. 最大单词长度乘积</a>
 */
public class Solution318 extends BaseSolution {

    public int maxProduct(String[] words) {
        boolean[][] flag = new boolean[words.length][26];
        int max = 0;
        for (int i = 0; i < words.length; i++) {
            for (char c : words[i].toCharArray()) {
                flag[i][c - 'a'] = true;
            }
            for (int j = 0; j < i; j++) {
                boolean hasSame = false;
                for (int k = 0; k < 26; k++) {
                    if (flag[j][k] && flag[i][k]){
                        hasSame = true;
                        break;
                    }
                }
                if (!hasSame) {
                    max = Math.max(max, words[i].length() * words[j].length());
                }
            }
        }
        return max;
    }

    public static void main(String[] args) {
        Solution318 solution = new Solution318();
        System.out.println(solution.maxProduct(new String[] {
                "abcw","baz","foo","bar","xtfn","abcdef"
        }));
    }
}